НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №6
з навчальної дисципліни “Програмування складних алгоритмів”
Тема:
РОЗРІДЖЕНІ МАТРИЦІ
Варіант №12
Київ 2022
Мета:
Метою лабораторної роботи є ознайомитися з основами роботи з розрідженими матрицями.
Теоретична частина
Розріджена матриця або розріджений масив є матриця в якому більшість елементів дорівнює нулю. Не існує чіткого визначення, скільки елементів повинно дорівнювати нулю, щоб матриця розглядалася розріджений але загальним критерієм є те, що кількість ненульових елементів приблизно відповідає кількості рядків або стовпців. На відміну від цього, якщо більшість елементів ненульові, тоді розглядається матриця щільний. Кількість нульових значень елементів, поділене на загальну кількість елементів (наприклад, m × n для матриці m × n), іноді називають розрідженість матриці. Типи зв'язаних списків
При зберіганні та маніпулюванні розрідженими матрицями на a комп'ютер, корисно і часто потрібно використовувати спеціалізовані алгоритми і структури даних які використовують переваги розрідженої структури матриці. Для розріджених матриць були створені спеціалізовані комп'ютери, оскільки вони поширені в галузі машинного навчання. Операції із використанням стандартних щільно-матричних структур та алгоритмів є повільними та неефективними при застосуванні до великих розріджених матриць як обробка та пам'яті витрачаються на нулі. Розріджені дані за своєю природою легше стиснута і, отже, вимагає значно менше зберігання. Деякі дуже великі розріджені матриці неможливо маніпулювати за допомогою стандартних алгоритмів щільної матриці.
Матриця зазвичай зберігається у вигляді двовимірного масиву. Кожен запис у масиві представляє елемент ai,j матриці і доступ до них здійснюється двома індекси i і j. Звичайно, i - індекс рядка, пронумерований зверху вниз, і j - індекс стовпця, пронумерований зліва направо. Для м × n матриці, обсяг пам'яті, необхідний для зберігання матриці в цьому форматі, пропорційний м × n (не враховуючи той факт, що розміри матриці також потрібно зберігати).
У випадку розрідженої матриці, істотне зменшення вимог до пам'яті може бути здійснено шляхом збереження лише ненульових записів. Залежно від кількості та розподілу ненульових записів можуть використовуватися різні структури даних, що приносить величезну економію пам'яті порівняно з базовим підходом. Компромісом є те, що доступ до окремих елементів стає більш складним, і необхідні додаткові структури, щоб мати можливість однозначно відновити вихідну матрицю.
Завдання:
Розробити спосіб економного зберігання в пам’яті розріджених матриць. Виконати індивідуальне завдання над стисненою матрицею. Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді.
Завдання до Варіанту_12
В кожному рядку масиву поміняти місцями елементи за наступною схемою: 1,2, 3,4 ↔ 5,6,7,8; 9,10,11,12 ↔ 13,14,15,16; …
Результати виконання лабораторної роботи:
\
Код:
//Лабораторна робота №6_ПСА
//ТР-15_Ткаченко_Майя, Варіант_12
#include <iostream>
using namespace std;
int getSize(int** arr, int rows, int cols)
{
if(!arr || rows <= 0 || cols <= 0) return 0;
int Size = 0;
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
if(arr[i][j] != 0) Size++;
}
}
return Size;
}
int main()
{
srand(time(nullptr));
const int rows = 6;
const int cols = 6;
int** arr = new int*[rows];
cout<<"\n============================>>>\n";
cout << "Ініційована матриця :\n " << endl;
cout<<"---------------------------------\n";
for (int i = 0; i < rows; ++i)
{
arr[i] = new int;
cout <<"||\t";
for (int j = 0; j < cols; ++j)
{
if(rand() % 2 == 0) //50% for zero
{
arr[i][j] = rand() % 10;
}
else
{
arr[i][j] = 0;
}...
